Natus Vincere được thành lập ngày 18 tháng 12 năm 2009. Sau sự sụp đổ của đội Ucraina KerchNET, các cựu thành viên của đội được hỗ trợ bởi Murat "Arbalet" Tulemaganbetov một người nổi tiếng và là nhà tổ chức các giải đấu thể thao điện tử lúc bấy giờ. Đội mới có tên "Arbalet UA", bao gồm Danylo "Zeus" Teslenko và Ivan "Edward" Sukharev từ Kharkiv, Sergey "starix" Ischuk từ Kiev, Arseniy "ceh9" Trynozhenko từ Lviv và Yegor "markeloff" Markelov từ Dnipropetrovsk. Đội hình Na`Vi.Counter-Strike thi đấu rất thành công và giành được nhiều giải thưởng quan trọng kể từ khi thành lập đến nay, luôn là 1 trong những đội mạnh nhất của bộ môn Counter-Strike trên toàn thế giới.